// 插入排序
// 将未排序数据插入到已排序序列的合适位置

// 外层循环：从数组的第二个元素开始遍历，将其视为未排序元素。
// 内层循环：将当前未排序元素与已排序序列中的元素从后往前比较，如果已排序元素大于当前元素，则将该已排序元素后移一位。
// 插入操作：当找到合适的位置后，将当前元素插入到该位置。


// 小→大 排序
function insertionSort(arr) {
  const len = arr.length;
  // 从第二个元素开始遍历数组，因为第一个元素可以看作是已排序的
  for (let i = 1; i < len; i++) {
    // 取出当前要插入的元素
    let current = arr[i];
    // 初始化 j 为当前元素的前一个位置
    let j = i - 1;
    // 当 j 大于等于 0 且前一个元素大于当前元素时
    while (j >= 0 && arr[j] > current) {
      // 将前一个元素后移一位
      arr[j + 1] = arr[j];
      // j 指针向前移动一位
      j--;
    }
    // 找到合适的位置插入当前元素
    arr[j + 1] = current;
  }
  return arr;
}

// 测试示例
const array = [5, 3, 8, 4, 2];
const sortedArray = insertionSort(array);
console.log(sortedArray);
